// 基数排序 空间换时间 时间复杂度：O(n*k)
function radixSort (arr) {
    // 数组中最大的数的位数
    let max = arr[0]
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i]
        }
    }
    let maxLength = max.toString().length
    // 定义一个二维数组 表示10个桶 每个桶就是一个一维数组
    let bucket = Array(10).fill(0).map(() => [])
    // 记录每次放入数据个数
    let bucketElementCounts = Array(10).fill(0)
    for (let i = 0, n = 1; i < maxLength; i++, n *= 10) {
        for (let j = 0; j < arr.length; j++) {
            let digitOfElement = ~~(arr[j] / n) % 10
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]
            bucketElementCounts[digitOfElement]++
        }
        // 按照这个桶的顺序
        let index = 0
        for (let k = 0; k < bucketElementCounts.length; k++) {
            // 如果桶中有数据才放回原数组
            if (bucketElementCounts[k] !== 0) {
                for (let l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index] = bucket[k][l]
                    index++
                }
            }
            bucketElementCounts[k] = 0
        }
        console.log(`第${i + 1}轮：`, arr)
    }
}

function main () {
    let arr = [53, 3, 542, 748, 14, 214]
    radixSort(arr)
}

main()